# 104. 图形排版(不懂)
# https://www.lanqiao.cn/problems/104/learning/?page=1&first_category_id=1&second_category_id=3&contain_answer=true
# Date:2025/1/19

def get_min_height_dp(m, n, pics):
    dp = [0] * (n + 1)

    def add(cur, k):
        if cur[0] + pics[k][0] <= m:
            cur[0] += pics[k][0]
            cur[1] = max(cur[1], pics[k][1])
        else:
            w = m - cur[0]
            cur[0] = m
            cur[1] = max(cur[1], (w * pics[k][1] + pics[k][0] - 1) // pics[k][0])
        return cur

    def get_dp(cur, k):
        while k < n and cur[0] < m:
            cur = add(cur, k)
            k += 1
        return cur[1] + dp[k]

    for i in range(n - 1, -1, -1):
        tmp = [0, 0]
        dp[i] = get_dp(tmp, i)
    ans = float("inf")
    h = 0
    cur = [0, 0]
    for i in range(n):
        ans = min(ans, h + get_dp(cur[:], i + 1))
        cur = add(cur, i)
        if cur[0] == m:
            h += cur[1]
            cur = [0, 0]
    return ans


if __name__ == '__main__':

    # 测试用例1
    print(get_min_height_dp(4, 3, [(2, 2), (2, 3), (2, 2)]))  # 2

    # 测试用例2
    pics = []
    with open("../data/104.in") as file:
        line = file.readline()
        m, n = map(int, line.split())
        line = file.readline()
        while line:
            pics.append(tuple(map(int, line.split())))
            line = file.readline()
    print(get_min_height_dp(m, n, pics))  # 625043
